// https://leetcode.cn/problems/candy/?envType=study-plan-v2&envId=top-interview-150

// 算法思路总结：
// 1. 使用贪心算法进行两次遍历分配糖果
// 2. 第一次从左到右遍历，处理右孩子评分更高情况
// 3. 第二次从右到左遍历，处理左孩子评分更高情况
// 4. 每次比较相邻孩子评分，确保高分孩子获得更多糖果
// 5. 最终累加所有孩子分配的糖果总数
// 6. 时间复杂度：O(N)，空间复杂度：O(N)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <numeric>
#include <string>

class Solution 
{
public:
    int candy(vector<int>& ratings) 
    {
        int m = ratings.size();
        
        vector<int> candyNums(m, 1);
        for (int i = 1 ; i < m ; i++)
        {
            if (ratings[i] > ratings[i - 1])
            {
                candyNums[i] = candyNums[i - 1] + 1;
            }
        }
        for (int i = m - 2 ; i >= 0 ; i--)
        {
            if (ratings[i] > ratings[i + 1])
            {
                candyNums[i] = max(candyNums[i], candyNums[i + 1] + 1);
            }
        }

        return accumulate(candyNums.begin(), candyNums.end(), 0);
    }
};

int main()
{
    vector<int> ratings1 = {1,0,2}, ratings2 = {1,2,2};
    Solution sol;

    cout << sol.candy(ratings1) << endl;
    cout << sol.candy(ratings2) << endl;

    return 0;
}